Сколькими
способами можно замостить прямоугольник 2 × n триоминошками? Триомино – это геометрическая фигура, составленная
из трех квадратов, соединяющихся между собой вдоль полного ребра. Есть только
две возможных триоминошки:
Например, замостить
прямоугольник 2 × 3 можно только тремя различными способами. Поскольку
ответ может быть достаточно большим, искомое количество способов следует
вычислять по модулю 106.
Вход. Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Каждая из следующих t строк содержит значение n
(0 < n < 109).
Выход. Для каждого теста в отдельной строке выведите количество
способов, которыми можно замостить прямоугольник 2 × n. Результат следует выводить по модулю 106.
Пример
входа |
Пример
выхода |
3 3 4 6 |
3 0 11 |
комбинаторика
Обозначим через
Un количество способов
замостить прямоугольник 2 × n с
помощью триомино. Обозначим через Vn
количество способов замостить прямоугольник 2 × n без угла 1 × 1 с помощью триомино.
Имеем следующие
начальные соотношения:
U1=
0, U2 = 0, U3 = 3
V1 =
0, V2 = 1, V3 = 0
Рассмотрим
возможные способы замощения прямоугольников Un и Vn.
Получим
следующие рекуррентные соотношения:
Исходя
из начальных условий, найдем U0 и V0:
, ,
Составим таблицу значений для Un и Vn:
n |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
Un |
1 |
0 |
0 |
3 |
0 |
0 |
11 |
0 |
0 |
41 |
0 |
0 |
153 |
Vn |
0 |
0 |
1 |
0 |
0 |
4 |
0 |
0 |
15 |
0 |
0 |
56 |
0 |
Сдвинем вторую строку на две позиции
влево. Тогда столбцы для индексов, не кратных 3, будут содержать только нули.
Удалим их. Перенумеруем новые столбцы. Таблица примет вид:
n |
0 |
1 |
2 |
3 |
4 |
Un |
1 |
3 |
11 |
41 |
153 |
Vn |
1 |
4 |
15 |
56 |
209 |
Рекуррентные
соотношения перепишутся в виде:
,
Или то же самое что
,
Рассмотрим
матрицу A = . A2 = , A3 = . Можно заметить, что первая строка матрицы An содержит значения Un-1
и Vn-1. Это
действительно так, потому что
* = =
Для решения задачи (нахождения значения Un) достаточно вычислить An+1 и вывести ее
элемент в левом верхнем углу. Возведение в степень совершаем за время O(log2n),
так как n < 109.
Все вычисления проводим по модулю 106.
Объявим модуль MOD, по которому будем проводить вычисления. Объявим класс
двумерной матрицы Matrix.
class Matrix
{
public:
long long a, b, c, d;
Matrix(long long a = 1, long long b = 0,
long long c = 0, long long d = 1)
{
this->a
= a; this->b = b;
this->c
= c; this->d = d;
}
Перегрузим оператор умножения матриц.
Matrix operator*
(const Matrix &x)
{
Matrix res;
res.a = (a * x.a + b * x.c) % MOD;
res.b = (a * x.b + b * x.d) % MOD;
res.c = (c * x.a + d * x.c) % MOD;
res.d = (c * x.b + d * x.d) % MOD;
return res;
}
Перегрузим оператор возведения
матрицы в степень n.
Matrix operator^
(int n)
{
Matrix res, x(*this);
while(n
> 0)
{
if (n
& 1) res = res * x;
n >>= 1;
x = x * x;
}
return res;
}
};
Возводим матрицу в степень n.
long long
Solve(long long
n)
{
Matrix res(1,1,2,3);
res = res^n;
return res.a;
}
Основная часть
программы. Читаем входные данные. Если значение n не делится на 3, то ответ 0. Иначе делим n на 3 и возводим матрицу в степень n + 1.
scanf("%d",&tests);
while(tests--)
{
scanf("%d",&n);
if (n % 3)
{
printf("0\n");
continue;
}
n /= 3;
res = Solve(n+1);
printf("%d\n",res);
}